package hot;

import java.util.HashSet;
import java.util.Set;

/**
 * @author way
 * @create 2025-03-19 21:48
 */
public class _287_findDuplicate {
    public int findDuplicate1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) return num;
            set.add(num);
        }
        return -1;
    }

    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];  // slow跳一步，fast跳两步
            if (slow == fast) {// 指针首次相遇
                fast = 0;  // 让快指针回到起点
                while (true) {
                    if (slow == fast) return slow; // 如果再次相遇，就肯定是在入口处

                    slow = nums[slow];  // 两个指针每次都进1步
                    fast = nums[fast];
                }
            }
        }
    }
}
